1. Field of the Invention
This invention relates to a method and system for generating images using precomputed visibility information.
2. Description of Background
Real-time 3-D graphics display hardware has become increasingly powerful and affordable. The availability of this hardware has enabled computer and game-console applications to routinely display scenes containing tens of thousands of graphic primitives in each frame. With few exceptions these hardware display systems employ a Z-buffer based hidden surface removal algorithm.
The z-buffer hidden-surface removal algorithm solves visibility per-pixel by computing the Z (depth) value of each rasterized pixel (or fragment) of every primitive in the view frustum. During rasterization the Z value of the current fragment is compared to the existing Z value in the frame buffer and the color of the fragment is written to the frame buffer only if it is has a lower Z value than the existing value in the Z-buffer.
While this approach provides acceptable performance for relatively simple scenes, it can fail to provide adequate real-time performance for complex, realistic scenes. Such scenes tend to have high depth complexity which typically forces each element of the Z-buffer to be compared multiple times during the rendering of a single frame. Essentially all hidden surface samples that lie within the view frustum must be Z-rasterized and compared to the Z-buffer values to find the closest visible samples.
In some Z-buffer implementations the rasterizer often performs not only the Z determination and Z-buffer compare for all hidden fragments but also computes the complete rendering of hidden fragments, writing the resulting color to the frame buffer only if the corresponding Z value was closer than the existing Z-buffer value. For scenes of even modest depth complexity, this can result in wasted computation and diminished performance.
Other z-buffer implementations includes some type of “early-Z” rejection in which the color value of the fragment is not computed if its Z value is greater than the corresponding Z-buffer value. This can reduce rendering of hidden fragments but is only maximally effective if the graphic primitives are rendered in a back-to-front order.
Another improvement to the hardware Z-buffer is the integration of certain elements of the “Hierarchical Z-buffer” algorithm (Greenet al 1993) (Green N., Kass, M., Miller, G “hierarchical Z-Buffer Visibility” Proceedings of ACM Siggraph 1993 pp. 231-238, the entirety of which is incorporated herein by reference) This algorithm employs a hierarchical representation of the Z-buffer to perform rapid visibility rejections tests. The complete hierarchical Z-buffer algorithm has proven difficult to implement in hardware although basic versions of the hierarchical Z-buffer pyramid itself has been implemented in some systems (e.g., Nvidia, ATI). In these implementations a low resolution version of the Z-buffer is maintained in memory that is local to the individual rasterizer units. These local representations are used in the previously described “early-Z” rejection test. If an individual fragment can be rejected by comparing it to the low resolution, locally stored Z-buffer element, then a slower access of the high resolution (non-local) Z-buffer is avoided.
In these accelerated hardware z-buffer systems “early-Z” rejection can sometimes prevent rendering of hidden fragments and hierarchical-Z pyramid can speed the “early-Z” rejection test. Nevertheless such accelerated systems still require that all primitives within the view frustum are processed through the geometry phase of the graphics pipeline and all fragments, including occluded surfaces, in the view frustum are processed through at least the Z generation/rejection test phase. Consequently, these systems can still perform poorly when rendering scenes of high depth complexity.
Given the relatively poor performance of Z-buffer systems for scenes of high depth complexity, algorithms have been developed which identify occluded geometry and exclude such geometry from both the geometry and rasterization stages of the hardware graphics pipeline. These occlusion culling techniques can be performed either at run-time or in a preprocessing stage. A review of visibility culling techniques is published in Cohen-Or et. al. (2003) (Cohen-Or, Daniel, et al. “A Survey of Visibility for Walkthrough Applications.” IEEE Transactions on Visualization and Computer Graphics 9.3 (2003): 412-31. Print., the entirety of which is incorporated herein by reference.) Visibility culling refers to any method which identifies and rejects invisible geometry before actual hidden surface removal (i.e. by Z-buffer) is performed. The well established methods of backface culling and view frustum culling using hierarchical techniques are routinely employed by applications to cull graphics primitives from the hardware pipeline. Occlusion culling is a type of visibility culling approach which avoids rendering primitives that are occluded in the scene. Occlusion culling involves complex interrelationships between graphic primitives in the model and is typically far more difficult to perform than view frustum culling.
In general, run-time occlusion culling techniques determine what geometry is visible from a single viewpoint. These are called “from-point” culling techniques. In contrast, preprocessing approaches to occlusion culling determine the subset of geometry that is visible from any viewpoint in a specified region. The latter methods are referred to as “from-region” visibility techniques.
The survey of Cohen-Or et. al. (2003) focuses on “walkthrough” type applications which are characterized by a relatively large amount of static geometry and high potential depth complexity. Many computer games, simulators and other interactive applications fall into this category. These applications tend to benefit substantially when “from-region” occlusion culling techniques are applied to the geometric database in a preprocessing step. These techniques partition the model into regions or cells. These viewcells are navigable regions of the model which may contain the viewpoint. During preprocessing the subset of graphics primitives that are potentially visible from anywhere within a viewcell (potentially visible set or PVS) is determined. The principal advantage of from-region visibility techniques is that the considerable computational cost of occlusion culling is paid in a preprocessing step rather than at runtime.
In general, from-region visibility preprocessing techniques aim to compute a conservative overestimate of the exact PVS for a view cell. The first from-region visibility methods were developed for interactive viewing of architectural models. Architectural models are naturally subdivided into cells (eg. rooms, halls) and the visibility between cells occurs through connecting openings (doorways, windows) called portals. Airey (1990) exploited this structure in simple, axially aligned models. He demonstrated a method of identifying polygons visible through portals using an approximate, but conservative, shadow umbra calculation.
Teller (1992) (Teller, Seth, Visibility Computations in Densely Occluded Polyhedral Environments. Diss. U of California at Berkeley, 1992. Berkeley: U of California at Berkeley, 1992. GAX93-30757. ACM Portal., the entirety of which is incorporated herein by reference) and Sequin extended the method of cell-and-portal from-region visibility to non-axis aligned polygonal models which do not require user defined walls and portals. Teller employed a BSP tree defined by the polygons of the model (autopartition). The leafs of the BSP tree are necessarily convex polyhedra which may not be completely closed. These convex polyhedra are the visibility cells (or viewcells) of the model. Using cell adjacency information available in the BSP graph, the open regions on the boundary between adjacent cells are identified and enumerated as portals between visibility cells.
Thus, Teller exploited the structure of the BSP autopartition to reduce the from-region visibility problem to a more restricted and simplified problem of visibility through a sequence of polygonal portals. Teller showed that even for this relatively restricted visibility problem, the visibility event surfaces separating from-cell visible volumes and from-cell occluded volumes are usually quadric surfaces.
Teller determined cell-to-cell visibility by employing a test for the existence of extremal stabbing lines between cells through a portal or sequence of portals. In this method cell-to-cell visibility is determined by establishing the existence of at least one ray that originates in the source cell and penetrates a sequence of portals to connecting cells. For example, the existence of such a ray through four portals is given by an extremal stabbing ray which is incident on any four edges of the relevant portals. Such a ray is identified using a Plucker mapping in which lines in three space are mapped to planes in 5-space. The intersection of these four planes form a line in 5-space which is intersected with the Plucker quardic to produce at most two non-imaginary results. Each of these intersections corresponds to a line in 3-space which intersects the four portal edges, i.e. an extremal stabbing line. The cost of locating an extremal stabbing ray is O(n2) in the number of edges in the portal sequence. Because the stabbing is performed incrementally the overall cost is O(n3). The method employs singular value matrix decomposition which can exhibit numerical instability as a consequence of geometric degeneracies encountered in the stabbing sequence.
Teller also developed a method of computing the exact visible volume through a portal sequence: the antipenumbra volume. As previously noted this volume is, in general, bounded by both planar and quadric surfaces. In this method the edges of the portals are once again dualized to Plucker coordinates, with each line in 3-space representing the coordinates of a plane in 5-space. The planes corresponding to all edges in a portal sequence are intersected with each other, using higher dimensional convex hull computation, to form a polyhedron in 5-space. The intersection of the faces of this polyhedron with the Plucker quadric correspond to the extremal swaths, or visibility event surfaces between the portal edges. The intersection of the 5D faces with the Plucker quadric are not computed directly. Instead the intersection of the 5D edges with the Plucker quadric are computed. The intersection of the edges of the 5D polyhedron with the Plucker quadric correspond to extremal stabbing lines which bound the swaths. The intersections of these 5D edges with the Plucker quadric are identified by finding the roots of a quadratic equation. The swaths are identified indirectly by computing the intersections of the 5D edges with the Plucker quadric and examining the faces of the 5D polytope (edges in 3D) that share the 5D edge.
Each swath may be a component of the boundary of the antipenumbra or, alternatively may be entirely within the antipenumbra volume. A containment test is used to identify boundary swaths.
Teller found that the antipenumbra computation is difficult to implement robustly. This method requires high-dimensional linear programming computations and root finding methods which, together, are not sufficiently robust to be used for complex models.
Teller (1992) and Teller and Hanrahan (1993) (Teller, Seth J., and Pat Hanrahan. “Global Visibility Algorithms for Illumination Computations.” Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1993, the entirety of which is incorporated herein by reference) also developed a simpler technique to determine cell-to-cell visibility and cell-to-object visibility through a portal sequence. In this implementation the antipentumbra is conservatively approximated by a convex polyhedron. This “linearized” antipenumbra is bounded by separating planes of the portal sequence effectively forming a convex hull of the antipentumbra. The planes defining the boundary of the linearized antipentumbra are intersected with each other and with the bounding planes of the bsp leaf cell to determine visibility through the portal sequence.
Although the linearized antipentumbra method overestimates the cell-to-cell visibility through a portal sequence it is amenable to a robust implementation.
In 1996 John Carmack employed a method of precomputing cell-to-cell visibility for the computer game Quake. Carmack's method of visibility precomputation in Quake is somewhat similar to the linearized antipenumbra method described by Teller. In both Teller's and Carmack's method the geometric database is subdivided by a BSP tree in which large occluders (e.g. walls, floors) acted as splitting planes. The terminal leafs of such a subdivision are convex polyhedra which may have one or more non-closed boundaries, or portals. In both methods the portals between leaf cells are identified and cell-to-cell visibility is established using a linearized overestimate of the antipentumbra between the portals.
In Teller's method the linearized antipenumbra is constructed by pivoting from each portal edge to two specific extremal or “separating” vertices in the portal sequence: one in each halfspace of the portal. (An extremal vertex of a portal is a vertex that together with the original portal edge form separating planes between the two portals.) The extremal vertices chosen result in planes which have the portal and all other extremal vertices in the same halfspace.
In Carmack's implementation this pairwise, sequential intersection of linearized antipentumbra is used to establish the existence of cell-to-cell visibility in a portal chain. The actual intersection of the antipentumbra with objects in each cell is not performed. The results are stored as a cell-to-cell PVS for each leaf cell.
Carmack's 1996 implementation of Teller's algorithms established BSP spatial subdivision with through-portal cell-to-cell visibility as the preferred method of visibility precomputation for computer games. Subsequent 3-D computer game systems either derived directly from Carmack's Quake Code (e.g. Quake II, Quake III, and Valve Software's “Source” game engine) or unrelated to it (e.g. Epic Game's Inc. “Unreal” game engine) have adopted this method of precomputed occlusion culling for densely occluded polyhedral environments.
In all of these systems the modeled environments of the game are constructed using “level editing” tools to create the geometry of the walls, floors, ceilings and other stationary, potentially occluding elements of the environments. This geometry is then submitted to a preprocess that constructs a BSP tree from this geometry using conventional BSP algorithms. Typically a second preprocess is then invoked to calculate the cell-to-cell PVS for each leaf cell of the BSP tree using the previously described through-portal visibility method. The PVS for a particular leaf cell is typically stored as an efficient compressed bit vector which indicates the other the bsp leaf cells that are visible from the source cell.
During runtime display the specific leaf cell containing the current viewpoint, the viewpoint leaf cell, is established using a simple BSP algorithm. The PVS for the viewpoint leaf cell is read and the corresponding (potentially visible) leaf cells are then hierarchically culled with respect to the current view frustum using standard hierarchical view frustum culling methods. Those graphic primitives from PVS leaf cells that are within the view frustum are then sent to the hardware graphics pipeline. During runtime display various from-point occlusion culling methods such as from-point portal and anti-portal culling may also be employed to further limit which primitives are sent to the hardware graphics pipeline. Nevertheless the precomputed PVS is typically the working set of primitives on which runtime from-point culling is performed. Consequently the precomputed PVS is central to the runtime performance not only because its own occlusion-culling costs have already been paid in a preprocess but also because an accurate PVS can lower the cost of runtime from-point occlusion culling methods by limiting the amount of geometry on which they must operate.
Although the BSP/portal-sequence method of PVS precomputation is widely employed to enhance the performance of computer games and similar applications current implementations of the method have a number of shortcomings. As previously discussed, the use of a linearized approximation of the portal sequence antipentumbra can cause the method to significantly overestimate the size of the PVS.
Another limitation of the method is that it requires construction of a BSP from the potentially occluding geometry of the model (an autopartition). Spatial subdivision using a BSP tree which is well-balanced and space-efficient is known to be an inherently difficult problem (see pg. 96 TELLER (1992)). The best bounds on time complexity for tree construction tends is O(n3) for a tree of worst case size O(n2). With well chosen splitting heuristics BSPs of reasonable size can be produced for models of moderate complexity. However for larger models these time and space cost functions can make practical BSP construction and storage prohibitive. Consequently when employing the method users must often limit the number of primitives used to construct the BSP. Complex objects which contain large numbers of non-coplanar primitives are typically deliberately excluded as potential occluders because they would increase the time and space cost of BSP construction. Such objects are typically managed separately by the method which requires that the user (i.e. the level designer) designate the objects as “detail” objects which do not contribute BSP planes and do not function as occluders during the PVS precomputation. These detail objects can still function as potential occludees in the method. If a detail object is completely contained within a PVS leaf cell and the leaf cell is determined not to be part of the cell-to-cell PVS for a given viewpoint leaf cell then the detail object can be excluded from the PVS of the viewpoint leaf cell. Nevertheless by eliminating objects from consideration as potential occluders based on their geometric complexity instead of their occluding potential, the method can significantly overestimate the actual from-region PVS.
A related weakness of the BSP/portal-sequence method is that it can perform poorly for modeled environments other than architectural interiors. When applied to architectural interior models the method tends to naturally construct BSP leaf cells that correspond to rooms having portals which correspond to doors or windows. In contrast for open, outdoor scenes as well as many complex interior scenes visibility is less clearly governed by a closed-cell, open-portal relationship. In such scenes visibility is often limited primarily by freestanding occluders not associated with a relatively closed cell; or by the aggregation or fusion of multiple smaller occluders. The BSP/portal-sequence does not effectively account for the fusion of individual freestanding occluders when culling occluded geometry. Applying the BSP/portal-sequence method to such scenes can produce a very large BSP and very long portal sequences. Under these conditions the method tends to take a very long time to compute PVS's that are highly overestimated and inefficient at runtime. Applications that employ the BSP/portal-sequence method will typically avoid PVS precomputation for such scenes and may instead rely on from-point occlusion culling methods such as from-point portal culling, such as the dynamic antiportal method used by Valve Software's Source® game engine, which must be computed during runtime.
Teller's initial description of the portal sequence method included a technique of computing cell-to-primitive PVS by intersecting the linearized antipenumbra with individual primitives in bsp leaf cells. In practice this technique has not been adopted by Carmack or other existing systems in part because the storage costs of a cell-to-primitive PVS would be much higher than a cell-to-cell PVS.
Despite the variety of approximations that have been employed to simplify and expedite BSP/portal-sequence visibility preprocessing, it remains a computationally expensive process. Because the BSP/portal-sequence method overestimates the PVS, completely occluded graphic primitives may undergo expensive runtime processing despite being invisible in the scene. The computational cost of processing occluded primitives during runtime may be paid by the CPU, the GPU, or both. CPU processing may include view frustum culling, from-point portal culling, from-point anti-portal culling, as well as the CPU cost of batch primitive submission to the GPU. On the GPU side, occluded primitives may undergo both vertex processing and rasterization phases of the hardware graphics pipeline. One measure of the efficiency of precomputed occlusion culling is the degree of overdraw that occurs during runtime. Overdraw may occur during rasterization whenever a rasterized fragment must be compared to a non-empty entry in the Z-buffer. This non-empty entry in the Z-buffer resulted from earlier rasterization of a fragment at the same image-space coordinates. The earlier entry may be in front of or behind (occluded by) the current fragment. The situation must be resolved by a Z-buffer read and compare operation. The earlier entry is overwritten if its Z value is more distant than that of the current fragment. As previously described, modern hardware Z-buffer systems can sometimes prevent actual shading of occluded fragments using an “early-Z” rejection test which may include a hierarchical Z compare mechanism. Nevertheless completely occluded primitives that make it to the rasterization stage of the graphics pipeline will, at a minimum, have each of their rasterized fragments compared to a corresponding Z-buffer and/or its hierarchical equivalent. We adopt the convention that overdraw includes any “overlap” of fragments in image-space which will at least require a Z-compare operation.
When the BSP/portal-sequence method was applied to the architectural interiors of the game Quake it was found that an average overdraw of 50% but ranging up to 150% in worst cases. (Abrash 1997, pg. 1189, Abrash, Michael “Michael Abrash's Graphics Programming Black Book Special Edition”, 1997 The Corilois Group, the entirety of which is incorporated herein by reference). This level of overdraw was encountered for relatively simple models which have a maximum depth complexity on the order of 10 and in which the visible depth complexity is often intentionally minimized by carefully selecting the position of occluding walls and portals.
A later implementation of Carmack's visibility precomputation method is employed in ID Software's Quake III computer game. In this game the simulated environments have significantly more geometric detail than the original Quake game (approximately 40,000 polygons per level). As in the original game, levels are carefully designed to contain a variety of obstacles including right-angled hallways, walls behind doorways, stairways with U-turns, and other visibility barriers. These obstacles are intentionally arranged to limit visibility within the model and thereby reduce the size of the PVS for the model's visibility cells. Even with these visibility barriers the approximate cell-to-cell portal visibility calculation results in considerable overdraw during runtime display. When applied to Quake III levels the BSP/portal-sequence precomputation method generally results in typical overdraws of 80% with worst cases exceeding 300%. These results are obtained by measuring depth complexity during run-time walkthrough of typical Quake III levels using the -dc command line option. During these measurements care must be taken to control for the effect of multipass shading.
Thus even when the BSP/portal-sequence method is applied to modeled environments for which it is best suited, it is a computationally expensive and relatively ineffective method of from-region occlusion culling. Consequently more recent work has focused on from-region occlusion culling methods which can be applied to general scenes and which produce a more precise PVS at a reasonable computational cost.
Early conservative methods of general from-region occlusion culling were described in Cohen-Or et al. (1998) (Chrysanthou, Yiorgos, Daniel Cohen-Or, and Dani Lischinski. “Fast Approximate Quantitative Visibility for Complex Scenes.” Proceedings of the Computer Graphics International 1998. Washington, D.C.: IEEE Computer Society, 1998. 220, the entirety of which is incorporated herein by reference). In these methods, objects are culled only if they are occluded by a single, large, convex occluder. Unfortunately the presence of large, convex occluders is rarely encountered in actual applications.
More recently, methods of from-region visibility precomputation have been developed which attempt to account for the combined occlusion of a collection of smaller occluders (occluder fusion).
Durand et al. (2000) (Durand, Fredo, et al. “Conservative Visibility Preprocessing using Extended Projections.” Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. Proc. of International Conference on Computer Graphics and Interactive Techniques. New York: ACM Press/Wesley Publishing Co., 2000. 239-48, the entirety of which is incorporated herein by reference) proposed a method of from-region visibility precomputation that employs a conservative, image-space representation of occluders and occludees called the extended projection. In this method a conservative, pixel based, representation of a convex occluder is constructive by rasterizing the occluder primitives from eight different viewpoints corresponding to the vertices of the viewcell. The extended projection of the convex occluder is the intersection of its projection from these views. This intersection can be computed by rasterizing the occluder into a hardware Z-buffer and stencil buffer data structure, which together form the “extended depth buffer”. Occludees are conservatively represented as the union of the projections of their bounding boxes from the same viewcell vertices. Occludees are culled as invisible from the region if they are completely covered by an occluder in the extended depth buffer. The extended projections of multiple occluders aggregate on the extended depth buffer, which accounts for occluder fusion.
The method may use extended depth buffers corresponding a single set of six planes which surround the entire environment. Alternatively, consecutive sets of surrounding planes at increasing distances from the viewpoint cell can be employed. In this case aggregated occluders on a near plane can be reprojected, using a conservative convolution operator, to subsequent planes. This “occlusion sweep” reprojection approach is more effective in capturing the fusion of multiple, small occluders at varying distances from the viewpoint cell. This arrangement was used, for example, to account for occluder aggregation in a forest scene of high depth complexity.
The extended projection method employs a number of approximations which result in overestimation of the PVS. First, the size of potential occludees is always overestimated since the method does not use the projection of the occludee itself. Instead the bounding box of the occludee is projected. In addition a second approximation, the bounding rectangle of this projection, is used to compute the extended projection of the occludee. These consecutive approximations result in an overestimate of the size of the occludee and consequently reduce the precision of the PVS. Moreover, the requirement to use occludee bounding boxes effectively limits the precision of the method to producing to a cell-to-object (rather than cell-to-primitive) PVS.
The extended projection method can directly rasterize only convex occluders into the extended depth buffer. Concave occluders must first be converted to a convex representation by intersecting the concave occluder surface with the projection plane. This is an additional step requiring a object-space calculation that, depending on the characteristics of the occludee surface, may be computationally expensive. In addition, if the location of the projection plane is not ideal, the intersection calculation can significantly underestimate the actual occluding effect of the concave occluder.
Another approximation employed by the extended projection method is the technique for reprojecting an occluder from one projection plane to a more distant one. The goal of this reprojection is effectively to identify the umbra of a planar occluder (with respect to a light source represented by the viewcell) and find the intersection of this umbra with a more distant plane. The extended projection method conservatively estimates this intersection by convolving the image of the occluder with an inverse image of rectangle that functions as an overestimate of a light source formed by the viewpoint cell. This technique can significantly underestimate the umbra of occluders which are similar in size to the viewpoint cell. By significantly underestimating the size of reprojected occluders the method will tend to overestimate the PVS.
A principal motivation of the extended projection method is to detect occlusion caused by the combined effects of multiple small occluders. Durand et al (2000). acknowledge that the method only detects fusion between occluders where the umbra (occluded region) of the occluders intersect and when this intersection volume itself intersects one of the arbitrarily chosen parallel projecting planes. Since relatively few projection planes are used in the occlusion sweep implementation, the method can frequently fail to detect occluder fusion caused by umbra which intersect outside the vicinity of a projection plane.
Schaufler et al. (2000) (Schaufler, Gernot, et al. “Conservative Volumetric Visibility with Occluder Fusion.” Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press/Wesley Publishing Co., 2000. 229-38, the entirety of which is incorporated herein by reference) developed a method of precomputing a conservative, from-region PVS that requires a volumetric representation of the modeled environment. In this method modeled objects must be bounded by closed surfaces. The closed bounding surface must produce a well defined interior volume for each object. The interior volume of an object is assumed to be opaque and is represented with convex voxels that are generated by a volumetric decomposition of the interior. The voxels act as occluders for the method. Occlusion is computed by finding a shaft which connects the viewpoint cell and a voxel. The extension of this shaft is an umbra within which all geometry is occluded. The method accounts for occluder fusion by combining adjacent voxels and by combining voxels and adjacent regions of occluded space. The implementation presented calculates a cell-to-cell PVS for 2D and 2.5D environments (e.g. cities modeled as heightfields). While the extension to full 3D environments is discussed by the authors, the computational and storage costs of a detailed volumetric representation of a 3D model are a real limitation of the method. While the volumetric visibility method of Schaufler et al. does not require occluders to be convex it does require them to be well-formed manifolds with identifiable solid (water-tight) interior volumes. This allows an individual occluder to be conservatively approximated by a box-shaped structure that is completely within the interior of the original occluder. This approximate occluder is generated by decomposing the interior into voxels and recombining the voxels in a process of blocker extension which attempts to maximize the size of the contained box-shaped approximate occluder. The method requires that the approximate occluders retain a box shape to facilitate the construction of the shaft used to determine occlusion. A principal limitation of this approach is that many occluders are poorly approximated by a contained box-shaped structure. In particular, concave objects or objects with topological holes (manifolds with genus greater than zero) present an ambiguous case to the blocker extension algorithm and significantly underestimate the occlusion caused by the object. A 2.5D implementation of the method described by Schaufler et al. to compute a PVS for viewcells in a city model was tested using primarily convex objects of genus zero. These objects tend to be reasonably well approximated using a box-shaped interior occluder. For more realistic models containing concave elements and holes (e.g. doors and windows) the method would be less effective in approximating occluders and consequently less efficient in culling occluded geometry.
The volumetric visibility method detects occluder fusion in cases where the linearized umbra of the occluders intersect. However, as with individual occluders, the blocker extension algorithm ultimately produces a simplified box-shaped approximation to the aggregate region of occlusion that can significantly underestimate the effect of occluder fusion.
Both the extended projection method and the volumetric visibility method effectively treat the viewcell as an area light source and respectively employ image-space and object-space techniques to compute a conservative, linearized approximation to the umbrae of polygon meshes. Algorithms for computing the shadow boundaries (umbra and penumbra) of a polygonal area light source, Nishita, Nakame (1985) (Nishita, Tomoyuki, Isao Okamura, and Eihachiro Nakamae. “Shading Models for Point and Linear Sources.” ACM Transactions on Graphics (TOG) 4.2 (1985): 124-46, the entirety of which is incorporated herein by reference) and Chin-Finer (1992) (Chin, Norman, and Steven Feiner. “Fast Object-Precision Shadow Generation for Area Light Sources Using BSP Trees.” Proceedings of the 1992 Symposium on Interactive 3D Graphics. Proc. of Symposium on Interactive 3D Graphics, 1992, Cambridge, Mass. New York: Association for Computing Machinery, 1992, the entirety of which is incorporated herein by reference) have also employed a conservative, linearized umbra boundaries.
These shadow boundary methods employ only the linear umbral event surfaces that form between a single convex polygonal light source and single convex polygons. The use of these methods on non-convex polygon meshes for instance would result in a discontinuous umbral event surface that would not accurately represent an umbral volume. Consequently their utility is practically limited to very simple models.
In 1992 Heckbert (Heckbert, P “Discontinuity Meshing for Radiosity”, Third Eurographics Workshop on Rendering, Bristol, UK, May 1992, pp 203-216, the entirety of which is incorporated herein by reference) used a different approach called incomplete discontinuity meshing to construct the exact linear visibility event surfaces (umbral and penumbral) cast by simple polygon models from an area light source. In this technique the linear event surfaces, or wedges, are formed between the edges of the light source and the vertices of the occluder and between the vertices of the light source and the edges of the occluders. The wedges are intersected with all of the model polygons and the segments of the polygons that are actually visible on the wedge are subsequently determined using a 2D version of the Weiler-Atherton object-space from-point visibility algorithm (Weiler, Kevin, and Peter Atherton. “Hidden Surface Removal using Polygon Area Sorting.” Proceedings of the 4th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1977. 214-22, the entirety of which is incorporated herein by reference).
The primary motivation of the discontinuity meshing method is to identify discontinuity boundaries within the penumbra. These boundaries can be used to increase the precision of illumination calculations within the penumbra. Unfortunately because the incomplete discontinuity meshing method constructs only the exact linear umbral event wedges, it generally fails to produce the complete, continuous umbral event surface. This is because for all but the simplest models, the continuous umbral event surface (for example incident on the silhouette contour of a polygon mesh) is formed by both planar and quadric visibility event surfaces. Consequently the method of incomplete discontinuity meshing is unsuited to identify mesh polygon or mesh polygon fragments that are visible or occluded from an area light source (or viewcell).
In the prior-art method of incomplete discontinuity meshing, all of the visibility event surfaces are formed by a vertex and an edge. FIG. 53 is from the prior-art method of incomplete discontinuity meshing by Heckbert. The figure shows an exact linear visibility event surface, or wedge, as the shaded triangular structure WEDGE R. The wedge labeled WEDGE R is incident on an edge e of a polygon and also incident on a vertex v, which may be a vertex of a light source. In the method of incomplete discontinuity meshing, the linear event surfaces are not defined over segments of an edge which are not visible from the vertex. In the case of FIG. 53, WEDGE R is not defined over the segment of edge e labeled GAP E, because polygon O occludes vertex v from GAP E. Because the wedge is not defined over this segment, the wedge's intersection with polygon P causes a corresponding gap between SEG1 and SEG2. If wedge R was an umbral wedge, its intersection with P would produce an incomplete umbral boundary. As a result of these gaps, the linear visibility event wedges constructed by the method of incomplete discontinuity meshing cannot be used alone to define umbral boundaries (or from-region visibility boundaries).
Drettakis and Fiume (1994) (Drettakis, George, and Eugene Fiume. “A Fast Shadow Algorithm for Area Light Sources Using Backprojection.” Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1994. 223-30, the entirety of which is incorporated herein by reference) completely characterized the visibility event surfaces that arise between a polygonal light source and objects in a polyhedral environment. In the method, called complete discontinuity meshing, both umbral and penumbral event surfaces are identified and intersected with model polygons. These intersections partition the model geometry into a “complete discontinuity mesh” such that in each face the view of the light source is topologically equivalent. The discontinuity mesh is shown to be a useful data structure for computing global illumination within the penumbra.
In the complete discontinuity meshing method four types of event surfaces between an area light source (called the “emitter”) and polyhedral mesh objects are identified. Two of these event surfaces are planar and two are quadrics.
The first type of visibility event surface identified is formed between a vertex or edge of the emitter and specific edges or vertices of the polyhedral model. These polygons are called an emitter-VE or (E-EV) wedges. The authors emphasize that not all vertices of a polyhedral mesh support an E-EV wedge. Only those mesh edges which are from-point silhouette edges (which they call “shadow edges”) for any point on the emitter surface will support a wedge. By defining “from-region silhouette edge” in this way all mesh edges which support an umbral or penumbral E-EV wedge are identified.
The other type of planar visibility event surface employed in complete discontinuity meshing is the Non-emitter-EV (NonE-EV) wedge. This type of wedge is potentially formed between any edge of the polyhedral mesh and any other edge such that the formed wedge intersects the emitter. For any edge of the polyhedral mesh the supported NonE-EV wedges occur only in a shaft formed between the edge and the emitter. This fact is used to construct identify the NonE-EV wedges.
A third type of visibility event surface is a quadric formed from an edge of the emitter and two edges of the polyhedral meshes. This is called a Emitter-EEE event or EeEEE surface. Such a surface is identified wherever two non-adjacent skew edges of the discontinuity mesh intersect. [This intersection actually corresponds to the intersection of a planar wedge with a from-region silhouette edge to form a compound silhouette contour]. The continuous visibility event surface at this point is a quadric surface.
The fourth and final type of visibility event surface formed between an area emitter and polyhedral mesh objects is the NonE-EEE. This is a quadric event surface formed between three skew edges of the polyhedral mesh such that the resulting quadric intersects the viewcell.
In the present specification the classification of from-region visibility event surfaces based on Drettakis and Fiume (1994) is adopted with some modification of the nomenclature to accommodate further subclassification. Table Ia includes the four types of visibility event surfaces originally proposed by Drettakis and Fiume (1994), renamed for clarity.
TABLE IaPrior Art Nomenclature of From-Region Visibility Event SurfacesVisibilty Event SurfaceDrettakis et al. NamingPlanar Event Surface Containing a Feature ofE-EVthe Emmitter/Viewcell/Source(Emitter-Edge Vertex)Planar Event Surface Not Containing aNonE-EVFeature of the Emitter/Viewcell/SourceQuadric Event Surface Containing a FeatureEmitter-EEE, EeEEof the Emitter/Viewcell/SourceQuadric Event Surface Not Containing aNon-EmitterEEEFeature of the Emitter/Viewcell/Source
Any of the four types of visibility event surfaces may ultimately contribute to the actual from-emitter (from-region) umbral boundary which separates the volume of space that is occluded from all points on the emitter from the volume of space visible from any point on the emitter. Unfortunately, using existing discontinuity mesh methods there is no a-priori way to determine which event surfaces will contribute to this umbral boundary that defines from-region visibility. Consequently, in order to use discontinuity meshing methods to identify the conservative, from-region umbral visibility event boundaries, all visibility event surfaces would first have to be generated and the resulting discontinuity mesh would have to be post-processed to determine which of the event surface-mesh polygon intersections represent true from-region umbel boundaries.
Several other problems limit the use of discontinuity meshing methods to compute conservative from-region visibility. The quadric event surfaces make a robust implementation of the event surface casting difficult. Event surfacing casting is required to find visible quadratic curve segments visible from the emitter edge (in the case of Emitter-EEE wedge). This on-wedge visibility is typically solved using a 2D implementation of Weiler-Atherton visibility algorithm which is difficult to implement robustly when using quadric surfaces.
As previously discussed, if the quadric surfaces are simply omitted (as in the method of incomplete discontinuity meshing) then continuous from-region umbral surfaces are not guaranteed, making determination of the from-region visible mesh polygons impossible.
Another important limitation of conventional discontinuity meshing methods is that they do not exhibit output-sensitive performance. This is because existing discontinuity meshing algorithms begin by generating all visibility event surfaces on all (from-region) silhouette edges of the polyhedral meshes. This includes silhouette edges that are actually occluded from the emitter/source. These event surfaces are then intersected with potentially each polygon of the polyhedral meshes, and the on-wedge visible segments are subsequently identified, using 2D Weiler-Atherton visibility, as a post-process. Since there is no depth-prioritization at any stage of theses algorithms they perform very poorly in densely occluded environments, where the majority of the boundaries generated would be inside the conservative from-region umbral boundary and therefore not contribute to the from-region visibility solution.
As shown later in this specification, the present method of visibility map construction using conservative linearized umbral event surfaces generated using an output-sensitive algorithm addresses many of the limitations of existing discontinuity meshing methods when applied to the problem of conservative from-region visibility.
Using the classification of from-region visibility event surfaces described by Drettakis and Fiume (1994) it is clear that the volumetric visibility method (Schauffler 2000) employs only E-EV surfaces to represent umbra boundaries. The extended projection method (as well as other projective methods) also implicitly use E-EV umbra boundaries.
A number of image-space techniques of conservative from-region visibility precomputation employ “shrunk occluders” to conservatively approximate visibility from a region using visibility from a single point in the region. The method of Wonka et al. (2000) (Wonka, Peter, Michael Wimmer, and Dieter Schmalstieg. “Visibility Preprocessing with Occluder Fusion for Urban Walkthroughs.” Proceedings of the Eurographics Workshop on Rendering Techniques 2000. London: Springer-Verlag, 2000. 71-82, the entirety of which is incorporated herein by reference) uses this approach to conservatively compute visibility from a region surrounding a viewpoint placed on the surface of a viewcell. Using multiple viewpoints placed on the surface of the viewcell, the visibility from the viewcell is computed as the combined visibility from the points. The distance between the viewpoints determines the magnitude of occluder shrinkage that must be applied to insure a conservative result. Since this method does sample visibility at multiple locations on the viewcell it does not a priori assume that all unoccluded elements are completely visible from the entire viewcell
In contrast to many of the previously described methods (including volumetric visibility and extended projection), the Wonka et al method does not assume that all unoccluded elements are completely visible from everywhere on the viewcell surface. Since it samples visibility from multiple locations on the viewcell it can approximate a backprojection which accounts for the partial occlusion of the viewcell from the unoccluded elements. The authors refer to this as penumbra effects, since elements in the penumbra of the viewcell/lightsource may give rise to planar (NonE-EV) umbra boundaries as well as quadric umbra boundaries (Emitter-EEE and Non-Emitter-EEE surfaces) that are more precise than the E-EV boundaries generated by assuming that the entire viewcell is visible from unoccluded elements. An implementation of the method is presented for 2.5D models in which the viewcells are rectangles. This greatly reduces the complexity of occluder shrinkage process and substantially reduces the number of viewpoint samples required compared to a full 3D implementation. Unfortunately, because the implementation is limited to 2.5D models it cannot be employed in most walkthrough applications.
Another method of visibility precomputation which employs “shrunk occluders” to approximate from-viewcell visibility using the visibility from a single point within the viewcell is described by Chhugani et al. (2005) (Chhugani, Jatin, et al. “vLOD: High-Fidelity Walkthrough of Large Virtual Environments.” IEEE Transactions on Visualization and Computer Graphics 11.1 (2005): 35-47, the entirety of which is incorporated herein by reference). This method employs a combination object-space and image-space approaches. In object-space the “supporting planes tangential to the viewcell and an object” are constructed. A viewpoint contained within these supporting planes is selected and for each supporting plane, an offset plane passing through the viewpoint and parallel to the original plane is constructed. According to the authors the intersection of the positive halfspaces of these offset planes comprises a frustum that is within the actual umbra of the original object. For each object polygon that generated a supporting plane, the shrinkage of the polygon is determined by the offset of the corresponding polygon to the chosen viewpoint. Occlusion behind an occluder object is determined by rendering the shrunk version from the viewpoint and then drawing the occludees using the occlusion query extension of the depth buffer. The query returns zero for occludees that are not visible. The method performs limited occluder fusion by rendering the shrunk occluders prior to occludees. The same viewpoint must be used to generate and render all shrunk occluders. This viewpoint must lie in the frusta of all the occluders. The location of the viewpoint is selected to maximize the sum of the volumes of the shrunk frusta using a convex quadratic optimization to achieve a local minimum solution.
The precision of the shrunk occluders is largely determined by the size and distribution of occluders being considered. Consequently the precision is not easily controlled in this method.
While the method admits non-convex occluders, including individual polygons and connected polygon meshes, it does not accommodate occluders that have holes. This is because the method depends upon each occludee having a single polyline “boundary” which is actually a type of from-region silhouette contour. This is a significant limitation since some large polygon meshes (e.g. buildings) which generally produce significant from-region occlusion also have multiple topological holes (e.g. doors and windows).
From the preceeding analysis it is clear that many existing methods of PVS precomputation employ conservative, linearized approximations to umbral boundaries based on simple E-EV event surfaces (e.g. extended projection, volumetric visibility) which assume that unoccluded elements are visible from everywhere on the viewcell (i.e. that the entire viewcell is visible from the unoccluded element).
Although existing primal-space methods of from-region visibility precomputation do not employ exact, quadric visibility event boundaries; other visibility applications do compute quadric visibility event surfaces in the primal-space. One of these applications, the Visibility Skeleton Durand (1997), is a data structure for answering global visibility queries. The other application, discontinuity meshing, is a method of computing illumination in the presence of area light sources. The discontinuity meshing method will be examined first.
As previously described, in the complete discontinuity meshing method of Drettakis and Fiume (1994), all of the visibility event surfaces arising between a polygonal light source and a polyhedral model are identified and intersected with model's polygons. These intersections comprise the “complete discontinuity mesh” of the model with respect to the source. The discontinuity mesh partitions the model geometry into a mesh of faces, such that in each face the view of the source is topologically equivalent. The complete discontinuity mesh is a useful data structure for computing global illumination near umbra and penumbra boundaries.
In the complete discontinuity meshing method four types of event surfaces are identified (see Table Ia and Ib). Two of these event surfaces are planar and two are quadrics. The two planar event surface types discussed previously, E-EV and NonE-EV, are used by the conservative from-region visibility event methods to conservatively contain the from-region umbral boundary surfaces. In some cases these planar surfaces are actually components of the exact umbra boundary formed by a silhouette edge and an a viewcell-as-lightsource.
The two types of quadric surfaces: Emitter-Edge-Edge-Edge (Emitter-EEE or EeEE) and Non-Emitter-Edge-Edge-Edge (Non-Emitter-EEE) are components of certain visibility event surfaces between the area light source and model polygons. For example, in some cases these quadric surfaces may be components of the exact umbra boundary formed by a silhouette edge and a viewcell-as-lightsource. In most cases these event surfaces are components of the penumbra. The discontinuity mesh methods describe techniques for identifying all of the quadric event surfaces that arise between the area light source and the model polygons.
For example in Drettakis and Fiume (1994) both Emitter-EEE and Non-Emitter-EEE event surfaces can be identified by forming a shaft between a generator edge and the convex hull of the emitter polygon. Emitter-EEE event surfaces are formed by the original edge, an edge of the emitter, and other edges in this shaft. Non-Emitter-EEE event surfaces are formed by the original edge and pairs of non-parallel edges in the shaft. Non-Emitter-EEE surfaces are those that intersect the emitter polygon. In both cases the ruled quadric event surface is identified using the parametric equation of the first generator edge:Pt=a1+t(b1−a1)where a1 and b1 are the endpoints of e1.
The value of t for a point Pt on the ruled quadric is found by forming the two planes containing point P and e2 and P and e3. The intersection of these two planes forms a line that is intersected with e1 
The valid interval of the ruled quadric on the generator edge is found by computing t for the endpoints a2 and b2 of edge e2 and for the endpoints a3 and b3 of edge e3. The intersection of the intervals is the valid region on the first generator edge. (This parametric representation of the ruled quadric was also suggested by Teller to represent the surfaces in 3D. However in Teller's method the ruled quadric visibility event surfaces are not actually identified in primal space. Instead their delimiters, the extremal stabbing lines, are identified in 5D line space.)
In the discontinuity meshing method once a quadric surface is identified by finding the valid intervals of its generator edges, the coefficients of the corresponding quadric equation:Ax2+By2+Cz2+Dyz+Exz+Fxy+Gx+Hy+Iz+J=0are determined. The intersection of this quadric surface with a model polygon is a quadratic curve. It is determined by transforming the three generating edges such that the polygon is embedded in the plane z=0. The quadratic curve is defined by the coefficients of the corresponding quadric equation minus all terms containing z. To generate the discontinuity mesh elements the quadratic curve is intersected with the edges of the model polygons and checked for visibility using a line sweep visibility processing algorithm.
In the discontinuity meshing method all visibility event surfaces involving an area light source and model polygons are identified. These visibility event surfaces include not only the umbral and extremal penumbra boundaries but many other event surfaces across which the topological view or “aspect” of the light source from the model geometry changes. In discontinuity meshing the visibility event surfaces are identified and intersected with the model polygons but specific bounding volumes of these surfaces, such as the umbra volume are not computed. These intersections in general produce forth degree space curves which can be difficult to solve robustly. Fortunately, the illumination calculations in which the discontinuity mesh is employed do not require the umbra volume to be represented.
The construction of the complete discontinuity mesh does require the event surfaces to be intersected with the model polygons, forming lines or quadratic curves on the surfaces of the polygons. These intersections are performed by casting the surfaces through the model. A regular grid-based spatial subdivision data structure is used to limit the number intersections performed. After all of the intersections are calculated a visibility step determines visible subsegments on the wedge. Consequently the construction of the discontinuity mesh is not output sensitive. and the cost of E-EV processing is expected O(n2) in the number of polygons. Quadric surfaces are also processed by finding first finding all of the quadratic curves formed by intersections of the quadric with model polygons, visibility on the quadric is resolved by a line sweep algorithm that is applied later, the cost of quadric processing is O(n6) in the number of polygons.
Like the complete discontinuity mesh, the visibility skeleton (Durand et al 1997) (Durand, Fredo; Drettakis, George; Puech, Calude; “The Visibility Skeleton: a Powerful and Efficient Multi-Purpose Global Visibility Tool, SIGGRAPH 1997 Proceedings, the entirety of which is incorporated herein by reference) is a data structure that accounts for quadric visibility event boundaries using primal space methods. The visibility skeleton is a complete catalog of visibility events that arise between edges in a polyhedral environment. In the visibility skeleton the visibility information of a model is organized as a graph structure in which the extremal stabbing lines are nodes of the graph and the visibility event surfaces are the arcs of the graph. The visibility skeleton can be used to answer visibility queries in the scene such as those that arise during global illumination calculations.
Unlike complete discontinuity meshing, the visibility skeleton avoids direct treatment of the line swaths that comprise the quadric visibility event surfaces. Instead the skeleton is constructed by directly computing only the extremal stabbing lines which bound the event surfaces themselves and which correspond to the nodes of the visibility skeleton graph structure.
In the general case of an extremal stabbing lines incident on four edges (EEEE nodes) the nodes are identified using the sets of tetrahedral wedges formed between the four edges. In this method an extended tetrahedron is formed between two of the edges as shown in FIGS. 8a, 8b and 8c of Durand et al (1997). The figures mentioned in this paragraph refer to the Durand et al (1997) paper. In FIG. 8a the extended tetrahedron formed by edge ei and ej is shown. In FIG. 8b a third edge ej is shown along with the segment of ej inside the extended tetrahedron formed by ei and ej. [The component of ej inside this extended tetrahedron will form a quadric visibility event (EEE) surface with ei and ej.] In FIG. 8c a fourth edge el is shown. This fourth edge el is similarly restricted by the three other extended tetrahedra which it may intersect: ekej, ekei, and ejei. The segment of el that is within all of these tetrahedral wedges could form three quadric surfaces with the other three edges. Only one line will actually intersect el and the other lines. This is the extremal Emitter-EEE line or node of the visibility skeleton involving these four edges. It is found by a simple binary search on the restricted segment of el. In this binary search an initial estimate of the intersection point P on el is chosen. The plane formed by this point and ei is then intersected with ej and e, giving two lines originating at P. The estimated intersection point P on el is refined by binary search until the angle between the two lines originating at P approaches zero. This occurs when the lines are congruent and therefore intersect ei, ej, ek, and el. The extremal lines so identified are intersected with model polygons using ray casting to determine if any scene polygons occlude the extremal line between its generating edges. If the line is so occluded no extremal stabbing line is recorded.
Other nodes of the visibility skeleton such as EVE, VEE, and EEV nodes form the limits of planar visibility event surfaces (eg. VE) and are also found by intersecting the relevant edges with corresponding extended tetrahedra.
The extremal stabbing lines so identified are stored explicitly as the nodes of the visibility skeleton. The visibility event surfaces (polygons or quadrics) that are bounded by these lines are not directly computed but instead stored implicitly as arcs in the graph. The component edges of the event surface are inferred from the nodes connected to the corresponding arc. Later use of the visibility skeleton for global visibility queries, such as discontinuity meshing in the presence of an area light source, may require the quadric surfaces to be generated directly using, for example, the parametric form of the quadric as described by Teller (1992).
From the preceeding analysis it is clear that both the discontinuity meshing and visibility skeleton methods include primal space techniques for identifying planar and quadric visibility event surfaces produced by area light sources. Both effectively employ the extended tetrahedral wedge test to identify quadric surfaces and the segments of the edge triples that support them. Both methods produce all of the visibility event surfaces between the relevant edges. Neither method is structured to efficiently generate only the from-region umbral boundary surfaces that are relevant in computing from-region visibility.
Another approach to computing from-region visibility is to transform the problem to line space and compute the umbra boundary surfaces using Plucker coordinates.
As previously described, the method of Teller (1992) developed the computational machinery necessary to compute the exact planar and quadric elements of an antipenumbra boundary of a portal sequence. This method transformed the problem to 5D line space.
The portal sequence is a significantly more restricted visibility problem than the general problem of visibility from an area lightsource (or equivalently a viewcell) in the absence of distinct portals. Moreover, to identify the quadric elements of the antipenumbra boundary Teller had to transform the problem to line space using Plucker coordinates and perform hyperplane intersections in 5D. This transformation increases the algorithmic complexity of the process and introduces potential robustness issues that are not present when working in the primal space.
Beginning in 2001 two groups of investigators Bittner (2001) (J. Bittner and J. P{hacek over ( )}rikryl. Exact Regional Visibility using Line Space Partitioning. Tech. Rep. TR-186-2-01-06, Institute of Computer Graphics and Algorithms, Vienna University of Technology, March 2001) and Nierenstein (2002) (Nirenstein, S., E. Blake, and J. Gain. “Exact From-Region Visibility Culling.” Proceedings of the 13th Eurographics Workshop on Rendering. Proc. of ACM International Conference Proceeding Series, Pisa, Italy, 2002. Vol. 28. Aire-la-Ville: Eurographics Association, 2002. 191-202, the entirety of which is incorporated herein by reference) developed methods to compute the exact viewcell to polygon PVS. Like Teller's exact antipenumbra calculation these methods require a transformation of the problem to Plucker coordinates and depend upon a combination of numerical techniques including singular value decomposition, robust root finding, and high-dimensional convex hull computations. Unlike Teller's approach these methods do not require an autopartition of the model into a BSP tree with enumerated portals.
In general, both of these exact methods, Niernstein (2002) and Bittner (2001), are structured as a visibility query which determines whether an unoccluded sightline exists between two convex graphic primitives (i.e. polygons). One of the tested polygons is a face of the viewcell, the other tested polygon is a mesh polygon of the modeled environment. The query determines if other polygons in the model, alone or in combination, occlude all the sightlines between the tested polygons. This occlusion query represents the linespace between the polygons by a 5-D Euclidean space derived from Plucker space. This mapping requires singular value matrix decomposition. In a subsequent step the method employs constructive solid geometry operations performed in 5 dimensional space. These processes, which form the basis of the visibility query, have a high computational cost. Moreover, because the fundamental organization of the method uses a polygon-to-polygon query, the cost on a naive implementation is O(n2.15) in the number of polygons (Nirenstein 2002).
The scalability of the method is improved over this worst-case by employing trivial acceptance and trivial rejection tests. Trivial acceptance of polygon-to-polygon visibility is established using a polygon-to-polygon ray casting query. If a ray originating at one test polygon reaches the other test polygon without intersecting any intervening polygons in the database then the visibility query can be trivially accepted. While this query has a lower computational cost than the exact Plucker space visibility query, it is itself a relatively expensive test for trivial acceptance. Trivial rejection of clusters of polygons can be accelerated by using a hierarchically organized database. If a query determines that the bounding box of an object is occluded with respect to a viewpoint cell then all of the polygons contained by the bounding box are also occluded. Furthermore, the method treats the occluded bounding box itself as a simple “virtual occluder.” (Koltun et al 2000) (Koltun, Vladen, Yiorgos Chrysanthou, and Daniel Cohen-Or. “Virtual Occluders: An Efficient Intermediate PVS Representation.” Proceedings of the Eurographics Workshop on Rendering Techniques 2000. London: Springer-Verlag, 2000. 59-70, the entirety of which is incorporated herein by reference). As defined by Koltun et al. (2000), a virtual occluder is not part of the original model geometry, but still represents a set of blocked lines. If the bounding box of an object is occluded then it can be used as an occluder for any geometry behind it. None of the polygons within the occluded bounding box need be considered as occluder candidates, as the bounding box itself is more than sufficient to test for occlusion of objects behind it. By employing these virtual occluders in conjunction with a front to back processing of scene objects Nirenstein et al (2000). significantly improved the scalability of the method from O(n2.5) to O(n1.15) for some tested scenes. Nevertheless, the method was shown to have a large constant computational overhead. For a densely occluded forest scene consisting of 7.8 million triangles preprocessing required 2 days 22 hrs on a dual Pentium IV 1.7 GHz multiprocessor. This compared to only 59 minutes preprocessing the same database using the extended projection method of Durand et al. implemented on a 200 MHz MIPS R10000 uniprocessor with SGI Onyx2 graphics hardware. The exact method culled an average of 99.12% of the geometry compared to 95.5% culling achieved with the conservative extended projection method.
One reason for the exact method's high computational cost is that the polygon-to-polygon occlusion query treats the occlusion caused by each polygon separately and does not explicitly consider the connectivity relationships between polygons to compute an aggregate occlusion. The exact method accounts for the combined occlusion of connected polygons only by the expensive 5-D constructive solid geometry process in which each polygon in processed separately. For this exact method the combined occlusion of connected polygons is determined only by the separate subtraction of individual 5-D polyhedra (representing the candidate occluding polygons) from a 5-D polytope (representing the cell-to-polygon sightlines). In the case of a connected mesh, the shared edges represent a trivial case of occluder fusion but for the exact method the fusion of these occluders must be explicitly computed and represent a degenerate case for the algorithm since the resulting polyhedra intersect exactly along the shared edges. In this sense the Niernstein et al. (2002) method completely neglects the important problem of identifying those specific edges of the polygon model which potentially support from-region visibility event surfaces (the potential from-region silhouette edges) and instead conducts the visibility query using all polygon edges.
In a later implementation, Nirenstein et al (2005) (Nirenstein, S., Haumont, D., Makinen, O., A Low Dimensioinal Framework for Exact Polygon-to-Polygon Occlusion Queries, Eurographics Symposium on Rendering 2005, the entirety of which is incorporated herein by reference) addressed this shortcoming of the method by identifying potential from-viewcell silhouette boundaries and constructing blocker polyhedra in 5D only along these boundaries. The definition of from-region silhouette edges employed in this method is essentially the same as that used in the earlier complete discontinuity meshing method of Drettakis et al. (1994) Although one test-bed implementation using this improvement accelerated the method by a factor of 30, the method still has a high constant computational overhead.
Besides being computationally expensive, the exact method is difficult to implement robustly. The singular value decompositions, robust root finding, and higher dimensional constructive solid geometry computations of the method tend to be very sensitive to numerical tolerances and geometric degeneracies.
Another shortcoming of the exact from-region method is that current implementations generally do not identify and remove occluded parts of partially occluded polygons. Current implementations of the method employ a polygon-to-polygon visibility query between the faces of the viewcell and the model polygons. The query is specifically structured to identify unoccluded regions between the tested polygon and to terminate early if any such regions are detected. Such implementations include an entire polygon in the PVS even if only a small part of it is visible from the viewcell. Consequently, although the PVS computed by these implementations may be the “exact” set of polygons visible from the region; the PVS may considerably overestimate the exposed surface area visible from the viewcell for large polygons. This can result in considerable overdraw at runtime. Modifying the exact from-region implementations to determine unoccluded fragments would substantially increase the computational cost and complexity of the implementation because: 1) the benefit of early termination would be lost, and 2) the boundaries between unocccluded and occluded fragments are quadratic.
Because these line-space methods compute the quadric umbra boundaries between source and target polygon they can provide an exact solution to this visibility query. In contrast, conservative methods of visibility precomputation employ less precise linearized umbra boundaries either explicitly (volumetric visibility) or implicitly (projective methods). However since these conservative methods operate in the primal space they are amenable to simpler, more robust implementations than the line space methods which require robust root finding and higher dimensional constructive solid geometry.
In both the extended projection method and the volumetric visibility method, as well as the exact from-region methods, a PVS is computed for parallelepiped viewcells that comprise a subdivision of navigable space. The use of parallelepiped viewcells has several advantages over the general convex polyhedral viewcells used by the BSP/portal sequence methods. The spatial subdivision defining the parallelepiped viewcells can easily be arranged as a spatial hierarchy (e.g. k-d tree) which facilitates a hierarchical approach to PVS determination. In this approach, used by both the extended projection and volumetric visibility methods, the PVS is determined for a viewcell at a high level in the hierarchy and is used as a working set to recursively determine the PVS of child viewcells lower in the hierarchy.
Another advantage of parallelepiped cells is that they have a simple cell adjacency relationship to neighboring cells. This relationship was exploited in the extended projection implementation, Durand et al. (2000) to implement a delta-PVS storage scheme. In this scheme the entire PVS for a number of key viewcells is stored. For most other viewcells, sets representing the differences of the PVS of adjacent viewcells are stored. This storage scheme substantially reduces the storage requirements for PVS data.
In the extended projection implementation the computed PVS encodes conservative viewcell-to-scene-graph-cell visibility at a coarse level of granularity. For this approximate solution the delta-PVS storage for 12,166 viewcells (representing 1/12th of the street area of a city model comprising 6 million polygons required 60 MB storage. Extrapolated, the storage of the delta-PVS data for the viewcells comprising all of the streets would be 720 MB. In the run-time portion all geometry is stored in main memory but the deltaPVS data is fetched from disk.
Another from-region visibility method which employs a delta-PVS storage scheme is the vlod method of Chhugani et al. (2005) In this implementation the from-region visibility solution provides a conservative viewcell-to-object PVS using a variation of the “shrunk occluder” method.
The delta-PVS is a list of object Ids referring to newly visible or newly invisible objects for a viewcell transition. In contrast to the extended projection method, the vlod implementation does not require all model geometry to be stored in main memory. Instead geometry is stored on disk and the current and predicted viewpoint locations are used to guide a speculative prefetch process which dynamically loads delta-PVS data and model geometry data. The model geometry is stored on disk using an object reordering scheme that reduces the number of disk accesses by storing together objects on the disk that tend to be fetched together. The delta-PVS data is also stored on disk. For a powerplant model of 13 million triangles and 500,000 viewcells, 7 GB is required to store the delta-PVS object ids.
At runtime the vlod implementation allows real-time rendering of models that are too large to be stored in main memory. Since the models rendered in the vlod implementation are not textured, the method does not address the storage and dynamic prefetch of texture information. In most modern walkthrough applications such as games, the amount of texture information for a model is typically much greater than the amount of geometry information.
The vlod system is an example of out-of-core, real-time rendering system that uses geometry prefetch based on precomputed from-region visibility. An earlier example by Funkhouser (Database Management for Interactive Display of Large Architectural Models, Proceedings of the conference on Graphics interface '96
Toronto, Ontario, Canada Pages: 1-8 Year of Publication: 1996 ISBN: 0-9695338-5-3, the entirety of which is incorporated herein by reference) of this approach used geometry PVS data computed using the portal sequence method. This implementation also used untextured geometry and, like vlod, does not address the prefetch of texture information.
Other out-of-core methods use geometry prefetch based on a run-time, conservative, from-point visibility method (e.g. prioritized layered projection or PLP) which is used to determine a conservative subset of the model visible from the viewpoint (IWALK, MMR). In one variation of this approach the process of primitive reprojection is used to directly identify model geometry that becomes newly exposed as a result of viewpoint motion (U.S. Pat. No. 6,111,582 Jenkins). These from-region visibility methods must be computed at runtime and therefore contribute to the overall runtime computational cost.
The goal of out-of-core rendering systems is to allow uninterrupted exploration of very large, detailed environments that cannot fit in core memory. Implemented effectively, this streaming approach can eliminate the frequent interruptions caused by traditional loading schemes in which entire sections (e.g. levels) of the environment are loaded until the next level is reached. Subdividing a complex 3D model into distinct “levels” drastically simplifies the loading and display of the graphics information while it forces the user to experience a series of disjoint locations, separated by load times that often disrupt the coherence of the experience.
The available data transfer rate between secondary storage and the core is a significant limiting factor for streaming implementations (Brad Bulkley, “The Edge of the World” Game Developer Magazine June/July 2006 pg. 19, the entirety of which is incorporated herein by reference). A delta-PVS storage scheme can substantially reduce the transfer rate required to stream prefetched data. Current delta-PVS implementations do not provide methods to manage texture information. Moreover they employ coarse-grained cell-to-object or cell-to-scenegraph-cell PVS data that is computed using imprecise from-region visibility computations which results in overestimated PVS/delta-PVS data. If the size of the delta-PVS data causes the prefetch process to exceed the available transfer rate between secondary storage and core memory then visibility errors can result.
A from-region visibility precomputation method capable of determining occluded polygon fragments and textures could produce a more precise cell-to-polygon PVS/delta-PVS than existing methods. This would reduce the transfer rate required to support streaming prefetch and also enhance the performance of the display hardware by reducing overdraw.